package com.objcat.playground.algorithm.sort.bubble;

/**
 * description: Bubble2 <br>
 * date: 2022/3/27 6:17 下午 <br>
 * author: objcat <br>
 * version: 1.0 <br>
 */
public class Bubble2 {

    static void bubbleSort(int[] list) {
        for (int i = 0; i < list.length - 1; i++) {
            for (int j = i; j < list.length - 1; j++) {
                System.out.println(list[i] + " " + list[j + 1]);
                if (list[i] > list[j + 1]) {
                    int temp = list[i];
                    list[i] = list[j + 1];
                    list[j + 1] = temp;
                }
            }
        }
    }

    static void printList(int[] list) {
        String result = "";
        for (int i = 0; i < list.length; i++) {
            if (i == 0) {
                result += "[" + list[i];
            } else if (i == list.length - 1) {
                result += ", " + list[i] + "]";
            } else {
                result += ", " + list[i];
            }
        }
        System.out.println(result);
    }

    public static void main(String[] args) {
        int[] list = {5, 3, 1, 4, 2};
        Bubble2.bubbleSort(list);
        printList(list);
    }
}

/**
 * 与冒泡排序法相似, 不同的是, 比较的是第一个数和其他数
 *
 * 从小到大: 当前数和其他数依次比较 只要比自己小就交换
 * 从大到小: 当前数和其他数依次比较 只要比自己大就交换
 *
 * 5 3 1 4 2
 * 1 3 5 4 2 第一轮 比 4 次
 * 1 2 5 4 3 第二轮 比 3 次
 * 1 2 3 4 5 第三轮 比 2 次
 * 1 2 3 4 5 第四轮 比 1 次
 *
 * 可以看到 5 个数字 比了 4 轮 第一轮比 4 次, 第二轮比 3 次 ... 第四轮比 1 次
 * 假设数组里有 n 个元素
 * 推理得出 需要比 n - 1 轮 每轮比了 n - 1 - i 次
 */